package com.zjsru.plan2024.oneday;

import java.util.HashMap;
import java.util.Map;

/**
 * 3164. 优质数对的总数 II
 *
 * @Author: cookLee
 * @Date: 2024-10-14
 */
public class NumberOfPairs2 {

    /**
     * 主
     * \
     * 输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
     * 输出：5
     * 解释：
     * 5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
     * \
     * 输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
     * 输出：2
     * 解释：
     * 2个优质数对分别是 (3, 0) 和 (3, 1)。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        NumberOfPairs2 numberOfPairs = new NumberOfPairs2();
        int[] nums1 = new int[]{1, 3, 4};
        int[] nums2 = new int[]{1, 3, 4};
        int k = 1;
        System.out.println(numberOfPairs.numberOfPairs2(nums1, nums2, k));
    }

    /**
     * 对数量:对于数据量大有超时
     *
     * @param nums1 nums1
     * @param nums2 nums2
     * @param k     k
     * @return long
     */
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        int ans = 0;
        for (int value : nums1) {
            for (int i : nums2) {
                if (value % (i * k) == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 配对数量2
     *
     * @param nums1 nums1
     * @param nums2 nums2
     * @param k     k
     * @return long
     */
    public long numberOfPairs2(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums1) {
            if (x % k != 0) {
                continue;
            }
            x /= k;
            for (int d = 1; d * d <= x; d++) {
                if (x % d > 0) {
                    continue;
                }
                cnt.merge(d, 1, Integer::sum);
                if (d * d < x) {
                    cnt.merge(x / d, 1, Integer::sum);
                }
            }
        }
        long ans = 0;
        for (int x : nums2) {
            ans += cnt.getOrDefault(x, 0);
        }
        return ans;
    }

    public long numberOfPairs3(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> count2 = new HashMap<>();
        int max1 = 0;
        for (int num : nums1) {
            count.put(num, count.getOrDefault(num, 0) + 1);
            max1 = Math.max(max1, num);
        }
        for (int num : nums2) {
            count2.put(num, count2.getOrDefault(num, 0) + 1);
        }
        long res = 0;
        for (int a : count2.keySet()) {
            for (int b = a * k; b <= max1; b += a * k) {
                if (count.containsKey(b)) {
                    res += (long) count.get(b) * count2.get(a);
                }
            }
        }
        return res;
    }
}
